#include <iostream>
using namespace std;
class ChessBoard{
private:
    const bool available;
    const int squares,norm;                     //norm为了将副对角线差变换到非负数
    bool *column,*leftDiagonal,*rightDiagonal;
    int *positionInRow,howMany;
    void putQueen(int);
    ostream & printBoard(ostream &);
    void initializeBoard();
public:
    ChessBoard();
    ChessBoard(int);
    ~ChessBoard();
    void findSolution();
};
ChessBoard::~ChessBoard() {
    delete [] positionInRow;
    delete [] column;
    delete [] leftDiagonal;
}
ChessBoard::ChessBoard():available(true),squares(8),norm(squares-1){
    initializeBoard();
}
ChessBoard::ChessBoard(int n):available(true),squares(n),norm(squares-1) {
    initializeBoard();
}
void ChessBoard::initializeBoard() {
    int i;
    column = new bool[squares];             //放置行
    positionInRow = new int[squares];       //放置位置
    leftDiagonal = new bool[squares*2-1];   //左边斜线
    rightDiagonal = new bool [squares*2-1]; //右边斜线
    for(i = 0;i<squares;i++)
        positionInRow[i] = -1;
    for(i=0;i<squares;i++)
        column[i] = available;
    for(i=0;i<squares*2-1;i++)
        leftDiagonal[i] = rightDiagonal[i] = available;
    howMany = 0;
}
void ChessBoard::putQueen(int row) {
    cout<<"函数开始：当前行为: "<<row<<"行,遍历不同的列col"<<endl;
    for (int col = 0; col < squares; col++){
        cout<<"for循环：循环开始在"<<row<<"行,"<<col<<"列!"<<endl;

        if(column[col] == available &&leftDiagonal [row+col] == available &&rightDiagonal[row-col+norm] == available) {
            cout<<"判断：经判断"<<col<<"列能放,列放置位置: "<<"("<<row<<","<<col<<")"<<"进入下一行:"<<row+1<<endl;
            //放置皇后在row
            positionInRow[row] = col;
            column[col] = !available;
            leftDiagonal[row+col] = !available;
            rightDiagonal[row-col+norm] = !available;
            if (row < squares-1)
                putQueen(row+1);
            else{
                printBoard(cout);
                howMany+=1;
                cout<<"找到第"<<howMany<<"个结果"<<endl;
            }
            column[col] = available;
            leftDiagonal[row+col] = available;
            rightDiagonal[row-col+norm] = available;
        }
        if(col==squares-1)
        {
            if(row-1>=0)
                cout<<"当前行遍历完成！跳到上一行"<<row-1<<endl;
        }

    }
}
ostream & ChessBoard::printBoard(ostream &os) {
//    cout<<"当前行为: "<<col<<"\n";
    return os;
}
void ChessBoard::findSolution() {
    putQueen(0);
    cout<<"\n";
    cout<<howMany<<" Solutions found.\n";
}

int main() {
    ChessBoard c1(4);
    c1.findSolution();
    return 0;
}